#include<bits/stdc++.h>
using namespace std;
const long long int N=105;
const long long int MOD=109;;
int n,m;
vector<int>path;
bool check[N];
int main()
{
    cin>>n>>m;
    long long  ret=n;
    m--;
    while(m--)
    {
       ret=(ret*(n-1))%MOD;
       
    }
    cout<<ret<<endl;
    return 0;
}